GermanWikipedia - /page/entry.mu

<!DOCTYPE html>

<title>Transfinite Induktion</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading">Transfinite Induktion</h1>

</header>

</div>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="de" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="de" dir="ltr">Transfinite Induktion ist eine <a href="Beweistechnik" class="mw-redirect" title="Beweistechnik">Beweistechnik</a> in der <a href="Mathematik" title="Mathematik">Mathematik</a>, die die von den <a href="Nat%C3%BCrliche_Zahlen" class="mw-redirect" title="Natürliche Zahlen">natürlichen Zahlen</a> bekannte <a href="Induktion_(Mathematik)" class="mw-redirect" title="Induktion (Mathematik)">Induktion</a> auf beliebige <a href="Wohlordnung" title="Wohlordnung">wohlgeordnete</a> Klassen verallgemeinert, zum Beispiel auf Mengen von <a href="Ordinalzahl" title="Ordinalzahl">Ordinalzahlen</a> oder <a href="Kardinalzahl_(Mathematik)" title="Kardinalzahl (Mathematik)">Kardinalzahlen</a>, oder sogar auf die echte <a href="Klasse_(Mengenlehre)" title="Klasse (Mengenlehre)">Klasse</a> aller Ordinalzahlen. Entsprechend ist die transfinite Rekursion ein Definitionsprinzip, das die <a href="Rekursion" title="Rekursion">Rekursion</a> bei natürlichen Zahlen verallgemeinert. Sie ist ein <a href="Deduktion#Mathematische_Logik_und_formale_Systeme" title="Deduktion">deduktives Verfahren</a>.

Die erste transfinite Rekursion führte <a href="Georg_Cantor" title="Georg Cantor">Georg Cantor</a> 1897 durch.<a href="#cite_note-1">[1]</a> <a href="Felix_Hausdorff" title="Felix Hausdorff">Felix Hausdorff</a> erhob sie zum allgemeinen Definitionsprinzip und führte auch die transfinite Induktion als Beweisprinzip ein.<a href="#cite_note-2">[2]</a>

<div class="mw-heading mw-heading2"><h2 id="Definition">Definition</h2></div>

Als transfinite Induktion gilt das folgende für eine wohlgeordnete Klasse <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (A,<)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (A,<)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/de55a41cc4e97dd40cced1fe4a24aca17e92541f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.394ex; height:2.843ex;" alt="{\displaystyle (A,<)}" loading="lazy"> erklärte Beweisschema:

<dl><dd>Will man beweisen, dass für alle <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a\in A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a\in A}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a97387981adb5d65f74518e20b6785a284d7abd5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.814ex; height:2.176ex;" alt="{\displaystyle a\in A}" loading="lazy"> die Aussage <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P(a)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P(a)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/87843d318d662e597ebd3c0260bcb2727707009d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.785ex; height:2.843ex;" alt="{\displaystyle P(a)}" loading="lazy"> gilt, so genügt es, die folgende Induktionsaussage zu beweisen:</dd>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a\in A}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a97387981adb5d65f74518e20b6785a284d7abd5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.814ex; height:2.176ex;" alt="{\displaystyle a\in A}" loading="lazy"> ist und für alle <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b\in A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b\in A}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/26329067b4b3630a2bb6f7e6b3ee367b70918371.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.581ex; height:2.176ex;" alt="{\displaystyle b\in A}" loading="lazy"> mit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b<a}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b<a}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ec536027666ac731c00e6db3a3b0b10d7ebbe031.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.326ex; height:2.176ex;" alt="{\displaystyle b<a}" loading="lazy"> die Aussage <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P(b)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P(b)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/356e0c99fe8fe21c22d83e4b43d4839e3e422344.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.552ex; height:2.843ex;" alt="{\displaystyle P(b)}" loading="lazy"> gilt, dann gilt auch <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P(a)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P(a)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/87843d318d662e597ebd3c0260bcb2727707009d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.785ex; height:2.843ex;" alt="{\displaystyle P(a)}" loading="lazy">.</dd></dl>

Dass diese bewiesene Induktionsaussage tatsächlich genügt, sieht man so ein: Sei <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B=\{x\in A\mid \neg P(x)\}}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle B=\{x\in A\mid \neg P(x)\}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a0e87da53edc02ed4e63c227bb9bb75bd952fb77.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:21.473ex; height:2.843ex;" alt="{\displaystyle B=\{x\in A\mid \neg P(x)\}}" loading="lazy">; das ist die Klasse aller Elemente von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy">, für die <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b4dc73bf40314945ff376bd363916a738548d40a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}" loading="lazy"> nicht zutrifft. Angenommen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle B}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/47136aad860d145f75f3eed3022df827cee94d7a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle B}" loading="lazy"> wäre nicht leer, dann gäbe es wegen der Wohlordnung ein kleinstes Element <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a\in B}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a\in B}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/739c140e9ae7f2a90119c5b40507d1ad2bc3396b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.834ex; height:2.176ex;" alt="{\displaystyle a\in B}" loading="lazy"> (welches <a href="O._B._d._A." class="mw-redirect" title="O. B. d. A.">o. B. d. A.</a> auch das Element ist, das die Aussage für kleinere Elemente <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b<a}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b<a}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ec536027666ac731c00e6db3a3b0b10d7ebbe031.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.326ex; height:2.176ex;" alt="{\displaystyle b<a}" loading="lazy"> beweist), und es gälte für jedes <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f11423fbb2e967f986e36804a8ae4271734917c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.998ex; height:2.176ex;" alt="{\displaystyle b}" loading="lazy"> mit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b<a}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b<a}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ec536027666ac731c00e6db3a3b0b10d7ebbe031.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.326ex; height:2.176ex;" alt="{\displaystyle b<a}" loading="lazy"> auch <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b\notin B}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b\notin B}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/eac9980d1cdc5e3a33d7506c56fe3956223b1c34.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.602ex; height:2.676ex;" alt="{\displaystyle b\notin B}" loading="lazy">, nach Definition von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle B}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/47136aad860d145f75f3eed3022df827cee94d7a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle B}" loading="lazy"> also <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P(b)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P(b)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/356e0c99fe8fe21c22d83e4b43d4839e3e422344.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.552ex; height:2.843ex;" alt="{\displaystyle P(b)}" loading="lazy">. Dann gilt aber nach der bewiesenen Induktionsaussage auch <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P(a)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P(a)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/87843d318d662e597ebd3c0260bcb2727707009d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.785ex; height:2.843ex;" alt="{\displaystyle P(a)}" loading="lazy">. Andererseits folgt jedoch aus <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a\in B}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a\in B}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/739c140e9ae7f2a90119c5b40507d1ad2bc3396b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.834ex; height:2.176ex;" alt="{\displaystyle a\in B}" loading="lazy"> sofort auch <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \neg P(a)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \neg P(a)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c7a22170874a06cbbaedfa60e236a4e56401a850.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.335ex; height:2.843ex;" alt="{\displaystyle \neg P(a)}" loading="lazy">. Wegen dieses Widerspruchs war die Annahme, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle B}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/47136aad860d145f75f3eed3022df827cee94d7a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle B}" loading="lazy"> sei nicht leer, falsch, so dass tatsächlich <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b4dc73bf40314945ff376bd363916a738548d40a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}" loading="lazy"> für alle Elemente von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy"> zutrifft.

<div class="mw-heading mw-heading2"><h2 id="Anwendung">Anwendung</h2></div>

Wenn <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy"> die Klasse der Ordinalzahlen ist, zerlegt man den Beweis oft in folgende drei Beweisschritte:

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P(0)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/60a4af3ee31a3a4e26e7cb20b4a6aed37f6e8a5e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.717ex; height:2.843ex;" alt="{\displaystyle P(0)}" loading="lazy"> ist wahr.</li>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ffd2487510aa438433a2579450ab2b3d557e5edc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.23ex; height:1.676ex;" alt="{\displaystyle a}" loading="lazy"> eine Ordinalzahl, so folgt aus <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P(a)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P(a)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/87843d318d662e597ebd3c0260bcb2727707009d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.785ex; height:2.843ex;" alt="{\displaystyle P(a)}" loading="lazy"> auch <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P(a+1)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P(a+1)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e2dfa91c02ef59e2bd5058140b37a5b5bcac548c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.787ex; height:2.843ex;" alt="{\displaystyle P(a+1)}" loading="lazy">.</li>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ffd2487510aa438433a2579450ab2b3d557e5edc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.23ex; height:1.676ex;" alt="{\displaystyle a}" loading="lazy"> eine <a href="Ordinalzahl" title="Ordinalzahl">Grenzzahl</a> und gilt <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P(b)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P(b)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/356e0c99fe8fe21c22d83e4b43d4839e3e422344.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.552ex; height:2.843ex;" alt="{\displaystyle P(b)}" loading="lazy"> für jede Ordinalzahl <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b<a}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b<a}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ec536027666ac731c00e6db3a3b0b10d7ebbe031.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.326ex; height:2.176ex;" alt="{\displaystyle b<a}" loading="lazy">, so gilt auch <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P(a)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P(a)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/87843d318d662e597ebd3c0260bcb2727707009d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.785ex; height:2.843ex;" alt="{\displaystyle P(a)}" loading="lazy">.</li></ul>

Die ersten beiden Schritte decken sich mit der <a href="Vollst%C3%A4ndige_Induktion" title="Vollständige Induktion">vollständigen Induktion</a> für natürliche Zahlen, denn die Menge der natürlichen Zahlen ist der bis an die erste Grenzzahl reichende Abschnitt der Klasse der Ordinalzahlen.

<div class="mw-heading mw-heading2"><h2 id="Transfinite_Rekursion">Transfinite Rekursion</h2></div>

Als transfinite Rekursion gilt folgendes Definitionsverfahren in einer wohlgeordneten Klasse <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (A,<)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (A,<)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/de55a41cc4e97dd40cced1fe4a24aca17e92541f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.394ex; height:2.843ex;" alt="{\displaystyle (A,<)}" loading="lazy">:

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(a)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/368cb4b81ba5754d7a354a4ce49c2f1084bdaace.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.318ex; height:2.843ex;" alt="{\displaystyle f(a)}" loading="lazy"> ausschließlich durch die Werte <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(b)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(b)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/adbef9aaf500c30a3f107e5d7efb7a8627d3bba9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.085ex; height:2.843ex;" alt="{\displaystyle f(b)}" loading="lazy"> an Stellen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b<a}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b<a}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ec536027666ac731c00e6db3a3b0b10d7ebbe031.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.326ex; height:2.176ex;" alt="{\displaystyle b<a}" loading="lazy"> definiert werden, so ist bereits hierdurch <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"> auf ganz <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy"> definiert.</dd></dl>

Dieses Rekursionsprinzip wird nun formalisiert für Ordinalzahlen.

Rekursionssatz:

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathrm {On} }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/df3720993ab82325279db5cae4b5c33066ed839b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.101ex; height:2.176ex;" alt="{\displaystyle \mathrm {On} }" loading="lazy"> sei die Klasse der Ordinalzahlen, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle V}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/af0f6064540e84211d0ffe4dac72098adfa52845.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.787ex; height:2.176ex;" alt="{\displaystyle V}" loading="lazy"> die <a href="Allklasse" title="Allklasse">Klasse aller Mengen</a> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R(x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R(x)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/cd5e851b43895fbe06436240dc7daa4d2033f082.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.903ex; height:2.843ex;" alt="{\displaystyle R(x)}" loading="lazy"> ein <a href="Term" title="Term">Term</a> als Rekursionsvorschrift. Dann gibt es genau eine transfinite Folge <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F\colon \mathrm {On} \to V}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F\colon \mathrm {On} \to V}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7505dda51ab94fab1061c757c2fc4c5042010889.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:11.277ex; height:2.176ex;" alt="{\displaystyle F\colon \mathrm {On} \to V}" loading="lazy">, so dass für alle Ordinalzahlen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ffd2487510aa438433a2579450ab2b3d557e5edc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.23ex; height:1.676ex;" alt="{\displaystyle a}" loading="lazy"> die Aussage <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F(a)=R(F|_{a})}">

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F(a)=R(F|_{a})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/3b8e39e3bb25d1c3fb604528c10c1ef27235d2fc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:14.941ex; height:3.009ex;" alt="{\displaystyle F(a)=R(F|_{a})}" loading="lazy"> gilt.

Beweisidee:

Man „vereinigt“ alle rekursiv definierten ordinalen Folgen mit derselben Rekursionsvorschrift zu einer transfiniten Folge. Die Rekursion für eine Ordinalzahl <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f11423fbb2e967f986e36804a8ae4271734917c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.998ex; height:2.176ex;" alt="{\displaystyle b}" loading="lazy"> erfasst folgende als <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P(b)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P(b)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/356e0c99fe8fe21c22d83e4b43d4839e3e422344.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.552ex; height:2.843ex;" alt="{\displaystyle P(b)}" loading="lazy"> bezeichnete Aussage:

<dl><dd>Es gibt genau eine Abbildung <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F_{b}\colon b\to V}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F_{b}\colon b\to V}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/51ca6053d8cf3c52553b6c16af5be8f851dd82d0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.865ex; height:2.509ex;" alt="{\displaystyle F_{b}\colon b\to V}" loading="lazy">, so dass für alle <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a<b}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a<b}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/91a7698e4c7401bb321f97888b872b583a9e4642.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.326ex; height:2.176ex;" alt="{\displaystyle a<b}" loading="lazy"> die Aussage <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F_{b}(a)=R(F_{b}|_{a})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F_{b}(a)=R(F_{b}|_{a})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/95380169d389d2b8dd2d0e4adc1fbd2ae200a421.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:16.324ex; height:3.009ex;" alt="{\displaystyle F_{b}(a)=R(F_{b}|_{a})}" loading="lazy"> gilt.</dd></dl>

Diese Abbildungen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F_{b}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F_{b}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b151118e130ddb3d3eea064479c152bd16738f81.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.432ex; height:2.509ex;" alt="{\displaystyle F_{b}}" loading="lazy"> erfüllen also dieselbe Rekursionsvorschrift, sind aber jeweils nicht auf der ganzen Klasse der Ordinalzahlen definiert. Aus der Eindeutigkeit ergibt sich jedoch, dass diese Funktionen Fortsetzungen voneinander sind und zu einer einzigen transfiniten Folge vereinigt werden können.

Die Gültigkeit von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P(b)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P(b)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/356e0c99fe8fe21c22d83e4b43d4839e3e422344.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.552ex; height:2.843ex;" alt="{\displaystyle P(b)}" loading="lazy"> für alle Ordinalzahlen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f11423fbb2e967f986e36804a8ae4271734917c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.998ex; height:2.176ex;" alt="{\displaystyle b}" loading="lazy"> zeigt man durch transfinite Induktion, und zwar wie oben angemerkt in drei Teilaussagen (es sei daran erinnert, dass für Ordinalzahlen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a<b}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a<b}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/91a7698e4c7401bb321f97888b872b583a9e4642.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.326ex; height:2.176ex;" alt="{\displaystyle a<b}" loading="lazy"> gleichbedeutend ist mit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a\in b}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a\in b}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4ac799f2a48fad4f92375610c33cbae9efab7030.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.068ex; height:2.176ex;" alt="{\displaystyle a\in b}" loading="lazy"> und dass <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b+1=b\cup \{b\}}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b+1=b\cup \{b\}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/605c33573fe0ee30f3dc7002b8f6d9793a2a9e76.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.001ex; height:2.843ex;" alt="{\displaystyle b+1=b\cup \{b\}}" loading="lazy">):

<ol><li>Die Aussage <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P(0)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P(0)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/60a4af3ee31a3a4e26e7cb20b4a6aed37f6e8a5e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.717ex; height:2.843ex;" alt="{\displaystyle P(0)}" loading="lazy"> ergibt sich unmittelbar, da es gar keine Ordinalzahlen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a<0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a<0}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e5d7ca60f6ed64b99649dcee21847295fedf206c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.491ex; height:2.176ex;" alt="{\displaystyle a<0}" loading="lazy"> gibt und die Rekursionsvorschrift trivialerweise gilt und da es ohnehin nur eine Abbildung <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0\to V}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0\to V}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0c7070430f8258a4273be7dd422240df845f98f1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.564ex; height:2.176ex;" alt="{\displaystyle 0\to V}" loading="lazy"> gibt.</li>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P(b)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/356e0c99fe8fe21c22d83e4b43d4839e3e422344.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.552ex; height:2.843ex;" alt="{\displaystyle P(b)}" loading="lazy">, dann gilt auch <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P(b+1)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P(b+1)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/75739d530afef90caa93a046ee193266108fb0a7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.555ex; height:2.843ex;" alt="{\displaystyle P(b+1)}" loading="lazy">: Die Existenz von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F_{b+1}\colon b+1\to V}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F_{b+1}\colon b+1\to V}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4768a5472fd54b2cca161af152ad53e93a624b9d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:15.968ex; height:2.509ex;" alt="{\displaystyle F_{b+1}\colon b+1\to V}" loading="lazy"> ergibt sich aus <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F_{b}\colon b\to V}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F_{b}\colon b\to V}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/51ca6053d8cf3c52553b6c16af5be8f851dd82d0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.865ex; height:2.509ex;" alt="{\displaystyle F_{b}\colon b\to V}" loading="lazy">, indem man <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F_{b+1}(a)=F_{b}(a)}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F_{b+1}(a)=F_{b}(a)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/1468745d4e6d9a9418078d1cbef5f6bbf54d9cab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.142ex; height:2.843ex;" alt="{\displaystyle F_{b+1}(a)=F_{b}(a)}" loading="lazy"> setzt, falls <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a<b}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a<b}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/91a7698e4c7401bb321f97888b872b583a9e4642.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.326ex; height:2.176ex;" alt="{\displaystyle a<b}" loading="lazy">, sowie (notwendigerweise) <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F_{b+1}(b)=R(F_{b})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F_{b+1}(b)=R(F_{b})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/3dc344061439c7f6430d58626387a13b1f2f071e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.444ex; height:2.843ex;" alt="{\displaystyle F_{b+1}(b)=R(F_{b})}" loading="lazy">. Ist <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{b+1}\colon b+1\to V}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{b+1}\colon b+1\to V}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/cf0ce399d3aaa38d8b6f60c62807733ffe538b40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:16.301ex; height:2.509ex;" alt="{\displaystyle G_{b+1}\colon b+1\to V}" loading="lazy"> eine Funktion nach denselben Bedingungen, so folgt zunächst <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{b+1}|_{b}=F_{b+1}|_{b}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{b+1}|_{b}=F_{b+1}|_{b}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0e3951f2ac66f718ad1237d64a04e7cca9d2d071.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:15.665ex; height:3.009ex;" alt="{\displaystyle G_{b+1}|_{b}=F_{b+1}|_{b}}" loading="lazy"> aus der Eindeutigkeitsaussage in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P(b)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P(b)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/356e0c99fe8fe21c22d83e4b43d4839e3e422344.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.552ex; height:2.843ex;" alt="{\displaystyle P(b)}" loading="lazy"> und dann aus der Rekursionsvorschrift auch <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{b+1}(b)=R(F_{b})=F_{b+1}(b)}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{b+1}(b)=R(F_{b})=F_{b+1}(b)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a451c92b04b68f811a8a13ec3e9eb595a59bcc61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:27.214ex; height:2.843ex;" alt="{\displaystyle G_{b+1}(b)=R(F_{b})=F_{b+1}(b)}" loading="lazy">, also insgesamt <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{b+1}=F_{b+1}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{b+1}=F_{b+1}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/50ac86e6b779487b420ce68a45ce42453ad03872.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:12.496ex; height:2.509ex;" alt="{\displaystyle G_{b+1}=F_{b+1}}" loading="lazy">.</li>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f11423fbb2e967f986e36804a8ae4271734917c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.998ex; height:2.176ex;" alt="{\displaystyle b}" loading="lazy"> Grenzzahl und gilt <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P(a)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P(a)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/87843d318d662e597ebd3c0260bcb2727707009d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.785ex; height:2.843ex;" alt="{\displaystyle P(a)}" loading="lazy"> für alle <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a<b}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a<b}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/91a7698e4c7401bb321f97888b872b583a9e4642.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.326ex; height:2.176ex;" alt="{\displaystyle a<b}" loading="lazy">, dann gilt auch <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P(b)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P(b)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/356e0c99fe8fe21c22d83e4b43d4839e3e422344.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.552ex; height:2.843ex;" alt="{\displaystyle P(b)}" loading="lazy">: Ist <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a<b}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a<b}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/91a7698e4c7401bb321f97888b872b583a9e4642.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.326ex; height:2.176ex;" alt="{\displaystyle a<b}" loading="lazy">, so gibt es <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/86a67b81c2de995bd608d5b2df50cd8cd7d92455.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.007ex; height:1.676ex;" alt="{\displaystyle c}" loading="lazy"> mit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a<c<b}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a<c<b}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7b5555ee657247e2c7c2b930cc75ba2349395d77.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:9.431ex; height:2.176ex;" alt="{\displaystyle a<c<b}" loading="lazy">. Man setze <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F_{b}(a)=F_{c}(a)}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F_{b}(a)=F_{c}(a)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ec1f5bd34b515d5ffe30702784a7113c854ae9d4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.048ex; height:2.843ex;" alt="{\displaystyle F_{b}(a)=F_{c}(a)}" loading="lazy">. Dies ist <a href="Wohldefiniertheit" title="Wohldefiniertheit">wohldefiniert</a>, da für <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c'}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c'}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f295e32663780aa8800e3106dba9d6e04e57cdc6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.692ex; height:2.509ex;" alt="{\displaystyle c'}" loading="lazy"> mit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a<c'<b}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a<c'<b}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/56dbe052e52d6108ef3d0a1444bad51cca2b0ee4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:10.116ex; height:2.509ex;" alt="{\displaystyle a<c'<b}" loading="lazy"> wegen der voraussetzbaren Aussagen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P(a),P(c),P(c')}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P(a),P(c),P(c')}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/02adf033e2594b00ae3e2be2ea638fdc583da0b0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.66ex; height:3.009ex;" alt="{\displaystyle P(a),P(c),P(c')}" loading="lazy"> gewiss <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F_{c'}(a)=R(F_{c'}|_{a})=R(F_{a})=R(F_{c}|_{a})=F_{c}(a)}">

<msub>

<msup>

</msup>

</mrow>

</msub>

<msub>

<msup>

</msup>

</mrow>

</msub>

<msub>

</mrow>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F_{c'}(a)=R(F_{c'}|_{a})=R(F_{a})=R(F_{c}|_{a})=F_{c}(a)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/eb702abaff1242a744d26f94fa90e02966a37ec4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:46.104ex; height:3.009ex;" alt="{\displaystyle F_{c'}(a)=R(F_{c'}|_{a})=R(F_{a})=R(F_{c}|_{a})=F_{c}(a)}" loading="lazy"> gilt. So ergibt sich auch die Eindeutigkeit.</li></ol>

Somit gilt die Aussage <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P(b)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P(b)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/356e0c99fe8fe21c22d83e4b43d4839e3e422344.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.552ex; height:2.843ex;" alt="{\displaystyle P(b)}" loading="lazy"> für alle Ordinalzahlen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f11423fbb2e967f986e36804a8ae4271734917c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.998ex; height:2.176ex;" alt="{\displaystyle b}" loading="lazy">. Man kann jetzt <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F\colon \mathrm {On} \to V}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F\colon \mathrm {On} \to V}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7505dda51ab94fab1061c757c2fc4c5042010889.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:11.277ex; height:2.176ex;" alt="{\displaystyle F\colon \mathrm {On} \to V}" loading="lazy"> definieren, indem man <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F(b)=F_{c}(b)}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F(b)=F_{c}(b)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e13cd22c8c9f173c75639bc9b58d9d725b9ce654.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.892ex; height:2.843ex;" alt="{\displaystyle F(b)=F_{c}(b)}" loading="lazy"> für ein beliebiges <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c>b}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c>b}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/14ec192db2a3f18a5eaf6fe93599f207ed02044e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.103ex; height:2.176ex;" alt="{\displaystyle c>b}" loading="lazy"> setzt. Dies ist wohldefiniert (also unabhängig von der Wahl von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/86a67b81c2de995bd608d5b2df50cd8cd7d92455.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.007ex; height:1.676ex;" alt="{\displaystyle c}" loading="lazy">), so dass man einfach auch <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c=b+1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c=b+1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/1bdea3ca048bce2a6e4e482e84ec1c7da81708a9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:9.106ex; height:2.343ex;" alt="{\displaystyle c=b+1}" loading="lazy"> wählen kann.

<div class="mw-heading mw-heading3"><h3 id="Anwendung_2">Anwendung</h3></div>

Wie bei der transfiniten Induktion kann man auch bei der transfiniten Rekursion statt mit einer Rekursionsvorschrift mit dreien arbeiten: mit einem Anfangsfunktionswert <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F(0)=R_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F(0)=R_{1}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2748e19e30f94431344e3464d16a471cee1d766e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.629ex; height:2.843ex;" alt="{\displaystyle F(0)=R_{1}}" loading="lazy">, einer Regel <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F(b+1)=R_{2}(F|_{b+1})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F(b+1)=R_{2}(F|_{b+1})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/83470bac23485b2ec8ce36cf9f21318c23cd5966.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:21.702ex; height:3.009ex;" alt="{\displaystyle F(b+1)=R_{2}(F|_{b+1})}" loading="lazy"> für Nachfolgerzahlen (oft in der einfacheren Form <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F(b+1)=R_{2}(F(b))}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F(b+1)=R_{2}(F(b))}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/8dd693a13e67e960804752fa5c2dd730738c2427.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:20.824ex; height:2.843ex;" alt="{\displaystyle F(b+1)=R_{2}(F(b))}" loading="lazy">) und einer Regel <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F(b)=R_{3}(F|_{b})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F(b)=R_{3}(F|_{b})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/5c1e897a4f7fce224d6ebf6bf12357a50ab89790.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:15.599ex; height:3.009ex;" alt="{\displaystyle F(b)=R_{3}(F|_{b})}" loading="lazy"> für Grenzzahlen. Die beiden ersten Rekursionsschritte decken sich mit der üblichen Rekursion für natürliche Zahlen.

<div class="mw-heading mw-heading3"><h3 id="Beispiele">Beispiele</h3></div>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/86a67b81c2de995bd608d5b2df50cd8cd7d92455.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.007ex; height:1.676ex;" alt="{\displaystyle c}" loading="lazy"> eine fest gewählte Ordinalzahl und die Rekursionsvorschrift <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy"> folgendermaßen gewählt: Falls <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"> der <a href="Funktionsgraph" title="Funktionsgraph">Graph</a> einer Funktion ist, sei <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R(f)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R(f)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/fb57f1b3ae288e52318d733f1c69d3e3637318b8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.852ex; height:2.843ex;" alt="{\displaystyle R(f)}" loading="lazy"> die kleinste nicht in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c\cup \operatorname {Bild} (f)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c\cup \operatorname {Bild} (f)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/084769fa96dfff9e15825529ff2101320006ccaf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.909ex; height:2.843ex;" alt="{\displaystyle c\cup \operatorname {Bild} (f)}" loading="lazy"> auftauchende Ordinalzahl (und ansonsten beliebig). Die hierdurch rekursiv (in Abhängigkeit von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/86a67b81c2de995bd608d5b2df50cd8cd7d92455.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.007ex; height:1.676ex;" alt="{\displaystyle c}" loading="lazy">) definierte Funktion <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/545fd099af8541605f7ee55f08225526be88ce57.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.741ex; height:2.176ex;" alt="{\displaystyle F}" loading="lazy"> liefert stets eine Ordinalzahl (folgt durch transfinite Induktion) und es gilt <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F(0)=c}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F(0)=c}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/9a4f60b957d72d5a615fbc704cb69ca7d40d22f9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.818ex; height:2.843ex;" alt="{\displaystyle F(0)=c}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F(1)=c+1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F(1)=c+1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/286d77e725bd893691d49f796a9730b8681ebe81.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.821ex; height:2.843ex;" alt="{\displaystyle F(1)=c+1}" loading="lazy"> usw. Man schreibt <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c+a}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c+a}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/df24e55bb815723ce2cccee641971ecff75a67d6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.077ex; height:2.176ex;" alt="{\displaystyle c+a}" loading="lazy"> für <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F(a)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F(a)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/fc7c034f57f1a8ef417737a9170547d644b6153b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.78ex; height:2.843ex;" alt="{\displaystyle F(a)}" loading="lazy"> und definiert so die Addition von Ordinalzahlen.</li>

<li>Die Addition kann auch – leichter nachvollziehbar – durch drei Rekursionsschritte definiert werden:

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c+0:=c}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/3bdc5df63b48bdf5f0d77bc541f19cc471bceeb6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:9.762ex; height:2.343ex;" alt="{\displaystyle c+0:=c}" loading="lazy">,</li>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c+(b+1):=(c+b)+1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/051fc558ee7f89e598e309136f39ddf793016b58.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:25.059ex; height:2.843ex;" alt="{\displaystyle c+(b+1):=(c+b)+1}" loading="lazy"> sowie</li>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c+b:=\sup\{c+a|a<b\}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/1ce9a89186e0cbc4bf90690975678fcd3bdd8f0c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:25.466ex; height:2.843ex;" alt="{\displaystyle c+b:=\sup\{c+a|a<b\}}" loading="lazy">, falls <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f11423fbb2e967f986e36804a8ae4271734917c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.998ex; height:2.176ex;" alt="{\displaystyle b}" loading="lazy"> Grenzzahl ist.</li></ul></li>

<li>Mit transfiniter Rekursion kann gezeigt werden: Jede wohlgeordnete Menge <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (A,<)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (A,<)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/de55a41cc4e97dd40cced1fe4a24aca17e92541f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.394ex; height:2.843ex;" alt="{\displaystyle (A,<)}" loading="lazy"> ist <a href="Ordnungsisomorphie" class="mw-redirect" title="Ordnungsisomorphie">ordnungsisomorph</a> zu einer Ordinalzahl. Beweisidee: Man versucht <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F\colon \mathrm {On} \to A}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F\colon \mathrm {On} \to A}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b8eed8337cae0dd7aa4c4e3765cac38c6c6321c2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:11.233ex; height:2.176ex;" alt="{\displaystyle F\colon \mathrm {On} \to A}" loading="lazy"> mittels der Rekursionsvorschrift <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R(f)=\min(A\setminus \operatorname {Bild} f)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R(f)=\min(A\setminus \operatorname {Bild} f)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0cf1890e582ab23d26223d48da4206ac23d4bf29.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:23.47ex; height:2.843ex;" alt="{\displaystyle R(f)=\min(A\setminus \operatorname {Bild} f)}" loading="lazy"> zu definieren. Hierbei wäre <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/545fd099af8541605f7ee55f08225526be88ce57.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.741ex; height:2.176ex;" alt="{\displaystyle F}" loading="lazy"> automatisch injektiv, was aber nicht sein kann, da <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy"> keine echte Klasse ist. Für die kleinste Ordinalzahl, an der die Rekursion scheitert, ergibt sich ein <a href="Ordnungsisomorphismus" title="Ordnungsisomorphismus">Ordnungsisomorphismus</a> mit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (A,<)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (A,<)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/de55a41cc4e97dd40cced1fe4a24aca17e92541f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.394ex; height:2.843ex;" alt="{\displaystyle (A,<)}" loading="lazy">.</li>

<li>Durch transfinite Rekursion wird auch die <a href="Kumulative_Hierarchie" class="mw-redirect" title="Kumulative Hierarchie">kumulative Hierarchie</a> von Mengen definiert.</li></ol>

<div class="mw-heading mw-heading2"><h2 id="Einzelnachweise">Einzelnachweise</h2></div>

<li id="cite_note-1"><a href="#cite_ref-1">↑</a> transfinite Rekursion zur Definition der Potenz von Ordinalzahlen, in: Cantor: <a rel="nofollow" class="external text" href="https://link.springer.com/article/10.1007/BF01444205">Beiträge zur Begründung der transfiniten Mengenlehre 2.</a>, in: <a href="Mathematische_Annalen" title="Mathematische Annalen">Mathematische Annalen</a> 49 (1897), §18, 231f.

</li>

<li id="cite_note-2"><a href="#cite_ref-2">↑</a> Felix Hausdorff: <a href="Grundz%C3%BCge_der_Mengenlehre" title="Grundzüge der Mengenlehre">Grundzüge der Mengenlehre</a>, Leipzig 1914, S. 112f <a rel="nofollow" class="external autonumber" href="https://archive.org/details/grundzgedermen00hausuoft/page/112/mode/2up">[1]</a>

</li>

</ol></div><div><div class="zim-footer">

Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2026-01-04" href="https://de.wikipedia.org/wiki/?title=Transfinite_Induktion&oldid=263021261">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.

</div>

</div></div>

</div>

</main>

</div>

</body></html>